package main

import "fmt"

func main() {
	wall := [][]int{
		{1, 2, 2, 1},
		{3, 1, 2},
		{1, 3, 2},
		{2, 4},
		{3, 1, 2},
		{1, 3, 1, 1},
	}
	fmt.Println(leastBricks(wall))

	wall = [][]int{
		{1},
		{1},
		{1},
	}
	fmt.Println(leastBricks(wall))

	wall = [][]int{
		{100000000, 100000000},
		{100000000, 100000000},
	}
	fmt.Println(leastBricks(wall))
}

func leastBricks(wall [][]int) int {
	//记录每一行离最左边距离的次数
	tempMap := make(map[int]int)
	for _, column := range wall {
		sum := 0
		//因为最右行缝隙不算所以到len-1位
		for _, row := range column[:len(column)-1] {
			sum += row
			tempMap[sum]++
		}
	}

	result := 0
	//找到距离最左边最多的缝隙
	for _, value := range tempMap {
		result = max(result, value)
	}
	//强的深度-最多缝隙数量=穿过最少砖块个数
	return len(wall) - result

}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
